Tree
Tree problems usually just spin around DFS or BFS and utilizes some specific tree properties so it's important to be able to implement these 2 algo while blindfolded
DFS
- The idea is usually to use recursion and recursively traverse the left and right subtree while performing some operation
- Sometimes it's helpful to use another params in the recursive function to keep track of some data (eg: path sum, current node path, etc)
Preorder Traversal
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.preorderTraversal(root.left)
right = self.preorderTraversal(root.right)
return [root.val] + left + right
- **Inorder Traversal
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val]+ right
- **Postorder Traversal
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
# We can use rootIndex of inorder because
# preorder: root + left + right
# inorder: left + root + right
# So we can use the rootIndex to split the preorder and inoder to 2 subarrays
rootIndex = inorder.index(root.val)
root.left = self.buildTree(preorder[1:rootIndex+1], inorder[:rootIndex+1])
root.right = self.buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
return root
# https://leetcode.com/problems/path-sum/
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def getSum(node, curSum):
if not node:
return False
if not node.left and not node.right and curSum + node.val == targetSum:
return True
left = getSum(node.left, curSum + node.val)
right = getSum(node.right, curSum + node.val)
return left or right
return getSum(root, 0)
- BFS
- The idea is to use queue to keep track of what to traverse next (we can use queue/stack for DFS too but recursion is usually cleaner)
# https://leetcode.com/problems/binary-tree-level-order-traversal/
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if not root:
return res
queue = [root]
while queue:
cur_level = []
cur_len = len(queue)
for i in range(cur_len):
node = queue.pop(0)
cur_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(cur_level)
return res
NOTES
An important property when dealing with Full Binary Tree is that it only has 2 childrens, from this we can calculate that:
Binary Tree in Array Representation If a binary tree is represented as an array:
1. **Index 0** represents the root node.
2. For a node at index i:
• **Left Child**: The left child is located at index 2i + 1.
• **Right Child**: The right child is located at index 2i + 2.Sometimes it is helpful to think of a Tree as a [[Graph]], and we can create an adjacency list from a Tree and then traverse it like a Graph or apply Graph algorithm.
Variants
Binary Search Tree
Definition: A tree where each node has at most two children, and for any node
- All values in the left subtree are less than the node's value
- All values in the right subtree are greater than the node's value
- In-order traversal yields sorted order
Efficeint for search, insert, and delete operations when balanced:
O(log n)These are some of the fundamental problems that demonstrate BST properties
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root
https://leetcode.com/problems/validate-binary-search-tree
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def helper(node, lower, upper):
if not node:
return True
if node.val >= upper or node.val <= lower:
return False
return helper(node.left, lower, node.val) and helper(node.right, node.val, upper)
return helper(root, float('-inf'), float('inf'))
https://leetcode.com/problems/insert-into-a-binary-search-tree
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
if val > root.val:
root.right = self.insertIntoBST(root.right, val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
return root
https://leetcode.com/problems/delete-node-in-a-bst
- Important algorithm to memorize
- 3 steps:
- Find the node to remove
- Replace the node by its successor (either smallest in right subtree or largest in left subtree)
- Remove the successor
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
def findSuccessor(node):
if node.left:
return findSuccessor(node.left)
return node
if not root:
return
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not root.left and not root.right:
return None
elif not root.left:
return root.right
elif not root.right:
return root.left
else:
successor = findSuccessor(root.right)
root.val = successor.val
root.right = self.deleteNode(root.right, root.val)
return root
Lowest Common Ancestor
https://leetcode.com/discuss/interview-question/6024811
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-ii
- Use the
helper/dfsfunction to both find the common ancestor and the existence of each node - Maintain 2 variables to keep track of the existence of each node
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
foundP = False
foundQ = False
def helper(node):
nonlocal foundP
nonlocal foundQ
if not node:
return
left = helper(node.left)
right = helper(node.right)
if node.val == p.val:
foundP = True
return node
if node.val == q.val:
foundQ = True
return node
if left and right:
return node
return left or right
res = helper(root)
return res if foundP and foundQ else None